#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include "t_tree.h"

const int INF = 0x3f3f3f3f;

Stack<int> TTree::S(0), TTree::S1(0);
List<ListNode> TTree::contour(0);
int TTree::count_ = 0;
std::vector<LIterator<Cube> > TTree::start_z, TTree::end_z;
List<Cube> TTree::cube_list_;
std::vector<int> TTree::cur_binary_tree_cubes_;
std::vector<int> TTree::determined_cubes_;

TTree::TTree(std::vector<Cube> &_cubes) : n_(_cubes.size()), cubes_(_cubes), nodes_(n_), computed_before_(false)//, S(n_), S1(n_)
{
	if (!count_++) {
		S.resize(n_);
		S1.resize(n_);
		contour.resize(n_ * 4 + 10);
		cube_list_.resize(n_ * 4 + 10);
		start_z.resize(n_);
		end_z.resize(n_);
		determined_cubes_.reserve(n_);
		cur_binary_tree_cubes_.reserve(n_);
	}
	change_node_1_ = change_node_2_ = -1;
	Generate();
	TreePacking();
}

void TTree::Generate()
{
	root_ = 0;
	nodes_[0].cube_id = 0;
	for (int i = 1; i < n_; ++i) {
		int p = rand() % i;
		while (nodes_[p][1] != -1 && nodes_[p][2] != -1 && nodes_[p][3] != -1)
			p = rand() % i;
		nodes_[i].cube_id = i;
		nodes_[i].parent = p;
		int child[5];
		child[0] = 0;
		for (int j = 1; j <= 3; ++j)
			if (nodes_[p][j] == -1) child[++child[0]] = j;
		nodes_[p][child[rand() % child[0] + 1]] = i;
	}
}

void TTree::ComputeVolume()
{
	computed_before_ = true;
	assert(determined_cubes_.size() == n_);
	int x_max = 0, y_max = 0, z_max = 0;
	for (std::vector<Cube>::iterator iter = cubes_.begin(); iter != cubes_.end(); ++iter) {
		x_max = std::max(x_max, iter->x + iter->length);
		y_max = std::max(y_max, iter->y + iter->width);
		z_max = std::max(z_max, iter->z + iter->height);
	}
	volume_ = x_max * y_max * z_max;
}

void TTree::SwapNode(int u, int v)
{
	change_node_1_ = u; change_node_2_ = v;
	std::swap(nodes_[u].cube_id, nodes_[v].cube_id);
	TreePacking();
}

void TTree::ModifyCube(int u, int k)
{
	change_node_1_ = u; change_node_2_ = -1;
	for (int i = 0; i < k; ++i) cube(u).rotate();
	TreePacking();
}

void TTree::PrintTree()
{
	//std::cout << "Node id -> Cube id" << ": ";
	std::cout << "digraph G {\n";
	//std::cout << "node [shape = record]\n";
	for (int i = 0; i < nodes_.size(); i++) {
		int u = nodes_[i].cube_id;
		std::cout << u << "[label = \" "<< u << " \" ] "<< std::endl;
		//std::cout << u << "[label = \" "<< "<l>|<m>"  << u << "|<r> \" ] "<< std::endl;
		// std::cout << u << "[label = \" "<< ":<l>|<m>"  << cubes_[u].length << " * " ;
		// std::cout << cubes_[u].width << " * "<< cubes_[u].height << "|<r> \" ] "<< std::endl;
	}
	std::string child[3] = {"red", "yellow", "blue"};
	std::cout << '\n';
	std::stack<int> S;
	S.push(root_);
	while (!S.empty()) {
		int u = S.top(); S.pop();
		//std::cout << "Current node:" << u << "\n";
		for (int i = 1; i <= 3; ++i) {
			int v = nodes_[u][i];
			if (~v) {
				std::cout << nodes_[u].cube_id << " -> " << nodes_[v].cube_id << "[color=\"" << child[i - 1] << "\"]\n";
				S.push(nodes_[u][i]);
				assert(nodes_[v][0] == u);
			}else {
				//std::cout << nodes_[u].cube_id << " -> " << -1 << "\n";
			}
		}
	}
	std::cout << "}\n";
}

void TTree::MoveNode(int u, int v)
{
	for (int t = v; t != -1; t = nodes_[t][0])
		if (t == u) return ;
	
	change_node_1_ = nodes_[u][0]; change_node_2_ = v;
	int child[10];
	child[0] = 0;
	for (int i = 1; i <= 3; i++)
		if (nodes_[v][i] == -1) child[++child[0]] = i;
	if (child[0] == 0) return ;
	// std::cout << "Move to " << v << " --" << child << "--> " << u << "\n";
	int parent = nodes_[u][0];
	for (int i = 1; i <= 3; i++) 
		if (nodes_[parent][i] == u) {
			nodes_[parent][i] = -1;
			break;
		}
	nodes_[u][0] = v;
	nodes_[v][child[rand() % child[0] + 1]] = u;
	TreePacking();
	return ;
}

bool TTree::CheckValid()
{
	std::stack<int> S;
	S.push(root_);
	int cnt = 0;
	std::vector<bool> vis(n_, bool(false));
	while (!S.empty()) {
		++cnt;
		int u = S.top(); S.pop();
		assert(vis[u] == false);
		vis[u] = true;
		for (int i = 1; i <= 3; ++i) {
			int v = nodes_[u][i];
			assert((bool(~v)) == (v != -1));
			if (~v) {
				S.push(nodes_[u][i]);
				assert(nodes_[v][0] == u);
			}
		}
	}
	assert(n_ == cnt);
	return true;
}

void TTree::TreePacking()
{
	visited_change_nodes = (false || !computed_before_);
	//CheckValid();
	cube_list_.clear();
	cube_list_.push_back(Cube(1, 1, 1, 0, 0, -INF));
	cube_list_.push_back(Cube(1, 1, 1, 0, 0, INF));
	cube_list_head_ = cube_list_.begin(); --cube_list_head_;
	determined_cubes_.clear();
	TreeDecomposition(root_);
	while (!S.empty()) {
		int u = S.top(); S.pop();
		TreeDecomposition(u);
	}
	ComputeVolume();
}

void TTree::TreeDecomposition(int u)
{
	assert(u > -1);
	cur_binary_tree_cubes_.clear();
	// First clear the contour.
	// We use a list named "contour" to maintain each point in the contour.
	contour.clear();
	// And add two boundary points.
	contour.push_back(ListNode(0, -INF));
	contour.push_back(ListNode(0, INF));
	cur = contour.begin();
	// Dfs and determine cube(u)'s cooridinates and update the stack S to do next decomposition.
	S1.push(u);
	while (!S1.empty()) {
		//std::cout << "decomp:" << u << "\n";
		u = S1.top(); S1.pop();
		PlaceModule(u);
		int *v = &(nodes_[u][1]);
		for (int i = 0; i < 2; ++i, ++v) {
			//std::cout << "subdecomp:" << u << "-->" << *v << "\n";
			if (~*v) {
				S1.push(*v);
				assert(*v == nodes_[u][1 + i]);
			}
		}
		//std::cout << "subdecomp:" << u << "-->" << *v << "\n";
		if (~*v) S.push(*v);
	}
	for (std::vector<int>::iterator iter = cur_binary_tree_cubes_.begin(); iter != cur_binary_tree_cubes_.end(); ++iter) {
		InsertX(*iter);
		determined_cubes_.push_back(nodes_[*iter].cube_id);
	}

}

void TTree::PlaceModule(int u)
{
	if (u == change_node_1_ || u == change_node_2_) visited_change_nodes = true;
	assert(u > -1);
	int p = nodes_[u].parent;
	// Update the z coordinate of cube(u).
	if (p == -1) cube(u).SetPos(0, 0, 0);
	else if (nodes_[p].left_child == u) cube(u).z = cube(p).z + cube(p).height;
	else cube(u).z = cube(p).z;
	// Update the x and y coordinate of cube(u).
	FindMaxY(u);
	FindMaxX(u);
	// Then cube(u) is determined.
	cur_binary_tree_cubes_.push_back(u);
}

void TTree::FindMaxY(int u)
{
	assert(u > -1);
	int z = cube(u).z, z2 = z + cube(u).height;
	// Move cur to the position that is below and nearest to the bottom of cube(u) in the Z-Y plane.
	while (cur->z < z) ++cur;
	while (cur->z >= z) --cur;
	int y_max = -1, sy = cur->y;
	// Remove items in the list and compute the maximum coordinate.
	for (++cur; cur->z < z2; ) {
		if (cur->z != z && y_max < cur->y) y_max = cur->y;
		contour.erase(cur++);
	}
	if (y_max < cur->y) y_max = cur->y;
	while (cur->z == z2) contour.erase(cur++);
	// Update the contour and the y coordinate of cube(u).
	int y2 = y_max + cube(u).width;
	contour.insert(cur, ListNode(sy, z));
	contour.insert(cur, ListNode(y2, z));
	contour.insert(cur, ListNode(y2, z2));
	contour.insert(cur, ListNode(cur->y, z2));
	cube(u).y = y_max;
}

// Brute force. Has been deprecated. (Not efficient.)
// void TTree::FindMaxX(int u)
// {
// 	if (!visited_change_nodes) return;
// 	// std::cout << "FindMaxX of cube " << nodes_[u].cube_id << "\n";
// 	assert(u > -1);
// 	int x_max = 0;
// 	for (std::vector<int>::iterator iter = determined_cubes_.begin(); iter != determined_cubes_.end(); ++iter)
// 		if (cubes_[*iter].intersect_y_z(cube(u))) {
// 			// std::cout << *iter << "\n";
// 			const Cube &c = cubes_[*iter];
// 			x_max = std::max(x_max, c.x + c.length);
// 		}
// 	cube(u).x = x_max;
// }

void TTree::FindMaxX(int u)
{
	assert(u > -1);
	int p = nodes_[u][0], z = cube(u).z, z2 = z + cube(u).height, x_max = 0;
	LIterator<Cube> iter;
	if (p == -1 || nodes_[p][3] == u) iter = cube_list_head_;
	else iter = start_z[p];
	while (iter->z + iter->height <= z) ++iter;
	start_z[u] = iter;
	if (!visited_change_nodes) return;
	for (; iter->z < z2; ++iter)
		if (iter->intersect_y_z(cube(u))) x_max = std::max(x_max, cube(iter->x).x + iter->length);
	cube(u).x = x_max;
}

void TTree::InsertX(int u)
{
	int p = nodes_[u][0], y = cube(u).y, z = cube(u).z;
	LIterator<Cube> iter;
	if (p == -1 || nodes_[p][3] == u) iter = cube_list_head_;
	else iter = end_z[p];
	for (; iter->z < z; ++iter);
	cube_list_.insert(iter, Cube(cube(u).length, cube(u).width, cube(u).height, u, y, z));
	end_z[u] = --iter;
}
